package leetcode_901_1000;

import java.util.*;

public class LeeCode_975 {
    public static void main(String[] args) {
//        System.out.println(oddEvenJumps(new int[]{10, 13, 12, 14, 15}));
//        System.out.println(oddEvenJumps(new int[]{2,3,1,1,4}));
//        System.out.println(oddEvenJumps(new int[]{5,1,3,4,2}));
        System.out.println(oddEvenJumps(new int[]{1,2,3,2,1,4,4,5}));
        System.out.println(oddEvenJumps2(new int[]{1,2,3,2,1,4,4,5}));
    }
    private static int oddEvenJumps(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            dp[i][1] = 1;
        }
        TreeMap<Integer, TreeSet<Integer>> map = new TreeMap<>();
        for (int i = 0; i < n; i++) {
            if (map.containsKey(arr[i])){
                map.get(arr[i]).add(i);
            }else {
                TreeSet<Integer> set = new TreeSet<>();
                set.add(i);
                map.put(arr[i], set);
            }
        }
        boolean[] tag = new boolean[n];
        for (int i = 0; i < n; i++) {
            Integer to = map.get(arr[i]).higher(i);
            if (to != null){
                dp[to][0] += dp[i][1];
                tag[to] = true;
            }else {
                Integer higher = map.higherKey(arr[i]);
                if (higher != null){
                    to = map.get(higher).higher(i);
                    if (to != null){
                        dp[to][0] += dp[i][1];
                        tag[to] = true;
                    }
                }
            }
            if (tag[i]){
                to = map.get(arr[i]).higher(i);
                if (to != null){
                    dp[to][1] += dp[i][0];
                }else {
                    Integer lower = map.lowerKey(arr[i]);
                    if (lower != null){
                        to = map.get(lower).higher(i);
                        if (to != null){
                            dp[to][1] += dp[i][0];
                        }
                    }
                }
            }
            map.get(arr[i]).remove(i);
            if (map.get(arr[i]).size() == 0)
                map.remove(arr[i]);
        }
        return dp[n - 1][0] + dp[n - 1][1];
    }
    private static int oddEvenJumps2(int[] arr) {
        int n = arr.length;
        int[][] dp = new int[n][2];
        for (int i = 0; i < n; i++) {
            dp[i][1] = 1;
        }
        PriorityQueue<int[]> min_q = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]){
                return o1[1] - o2[1];
            }
            return o1[0] - o2[0];
        });
        PriorityQueue<int[]> max_q = new PriorityQueue<>((o1, o2) -> {
            if (o1[0] == o2[0]){
                return o1[1] - o2[1];
            }
            return o2[0] - o1[0];
        });
        List<int[]> fa = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            fa.add(new int[]{arr[i], i});
        }
        min_q.addAll(fa);
        max_q.addAll(fa);
        boolean[] tag = new boolean[n];
        List<int[]> list = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            int[] p = null;
            min_q.remove(fa.get(i));
            max_q.remove(fa.get(i));
            while (!min_q.isEmpty()){
                int[] poll = min_q.poll();
                list.add(poll);
                if (poll[0] >= arr[i]){
                    p = poll;
                    break;
                }
            }
            if (p != null){
                int j = p[1];
                tag[j] = true;
                dp[j][0] += dp[i][1];
            }
            min_q.addAll(list);
            list.clear();
            p = null;
            if (tag[i]){
                while (!max_q.isEmpty()){
                    int[] poll = max_q.poll();
                    list.add(poll);
                    if (poll[0] <= arr[i]){
                        p = poll;
                        break;
                    }
                }
                if (p != null){
                    int j = p[1];
                    dp[j][1] += dp[i][0];
                }
                max_q.addAll(list);
                list.clear();
            }
        }
        return dp[n - 1][0] + dp[n - 1][1];
    }
}
